package _interview100;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 394. 字符串解码
 */
public class No394 {
    public String decodeString(String s) {
        Deque<Character> stack = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if (c == ']') {
                ArrayList<Character> list = new ArrayList<>();
                while (stack.peek() != '[') {
                    list.add(stack.pop());
                }
                stack.pop();
                int multi = 0;
                for (int i = 1; !stack.isEmpty() && Character.isDigit(stack.peek()); i *= 10) {
                    multi += (stack.pop() - '0') * i;
                }
                for (int i = 0; i < multi; i++) {
                    for (int j = list.size() - 1; j >= 0; j--) {
                        stack.push(list.get(j));
                    }
                }
            } else stack.push(c);
        }
        StringBuilder ans = new StringBuilder();
        while (!stack.isEmpty()) {
            ans.append(stack.pollLast());
        }
        return ans.toString();
    }
}
